Podciągi zmienne
Limit pamięci: 32 MB
W danym ciągu
poszukujemy podciągów zmiennych.
Podciąg ciągu otrzymujemy, usuwając z niego dowolną liczbę wyrazów (potencjalnie zero).
Formalnie, podciągiem ciągu
jest dowolny ciąg
, przy czym
.
Natomiast podciąg zmienny charakteryzuje się tym, że jego każde dwa
kolejne wyrazy są różne.
Dla przykładu, ciąg
jest podciągiem zmiennym
ciągu
.
Zastanawiamy się, ile różnych i niepustych podciągów zmiennych zawiera dany ciąg.
Podciągi uważamy za różne, jeśli zostały wybrane z innych zestawów
pozycji w ciągu
.
Przykładowo, ciąg
zawiera dwa różne podciągi zmienne
postaci
.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba
naturalna
(
), oznaczająca długość ciągu
.
Drugi wiersz zawiera
liczb całkowitych
(
).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program
powinien wypisać jedną liczbę całkowitą:
resztę z dzielenia przez
liczby niepustych podciągów
zmiennych ciągu podanego na wejściu.
Przykład
Dla danych wejściowych:
4
1 2 1 1
poprawną odpowiedzią jest:
9
Wyjaśnienie do przykładu:
Szukanymi podciągami ciągu
są:
-
- wliczany trzykrotnie,
-
- wliczany raz,
-
- wliczany raz,
-
- wliczany dwukrotnie oraz
-
- wliczany dwukrotnie.
Autor zadania: Jakub Radoszewski.